package basic.study.leetcode;

/**
 * @ClassName Hard4
 * @Description 寻找两个正序数组的中位数
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/16 17:06
 * @Version 1.0
 */
public class Hard4 {
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
            int len2 = nums2.length;
            int totalLen = len1 + len2;
            if (totalLen % 2 == 1) {
                int midIndex = totalLen / 2;
                double median = getKthElement(nums1, nums2, midIndex);
                return median;
            } else {
                int midIndex1 = totalLen / 2 -1;
                int midIndex2 = totalLen / 2;
                double median = getKthElement(nums1, nums2, midIndex1) + getKthElement(nums1, nums2, midIndex2);
                return median;
            }

        }
        //二分法，获取两有序数组的第k位数
        private int getKthElement(int[] nums1, int[] nums2, int k) {
            int index1 = 0;
            int index2 = 0;
            int len1 = nums1.length;
            int len2 = nums2.length;

            while (true) {
                if (index1 == len1) {
                    return nums2[index2 + k - 1];
                }
                if (index2 == len2) {
                    return nums1[index1 + k - 1];
                }
                if (k == 1) {
                    return Math.min(nums1[index1], nums2[index2]);
                }

                int half = k / 2;
                int newIndex1 = Math.min(len1, index1 + half);
                int newIndex2 = Math.min(len2, index2 + half);
                int pivot1 = nums1[newIndex1];
                int pivot2 = nums2[newIndex2];
                if (pivot1 <= pivot2) {
                    k -= (newIndex1 - index1 + 1);
                    index1 = newIndex1 + 1;
                } else {
                    k -= (newIndex2 - index2 + 1);
                    index2 = newIndex2 + 1;
                }
            }

        }


        public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
            double[] nums = new double[nums1.length + nums2.length];
            for(int i = 0; i < nums1.length; i++) {
                nums[i] = nums1[i];
            }
            for(int i = nums1.length; i < nums1.length + nums2.length; i++) {
                nums[i] = nums2[i - nums1.length];
            }

            int index = partition(nums, 0, nums.length-1);
            if (nums.length % 2 != 0) {
                while(index != nums.length/2 ) {
                    if(index > nums.length/2) {
                        index = partition(nums, 0, index-1);
                    } else {
                        index = partition(nums, index+1, nums.length -1);
                    }
                }
                return nums[index];
            } else {
                while(index != nums.length/2 ) {
                    if(index > nums.length/2) {
                        index = partition(nums, 0, index-1);
                    } else {
                        index = partition(nums, index+1, nums.length -1);
                    }
                }
                double val1 = nums[index];
                while(index != nums.length/2 -1 ) {
                    if(index > nums.length/2 -1) {
                        index = partition(nums, 0, index-1);
                    } else {
                        index = partition(nums, index+1, nums.length -1);
                    }
                }
                double val2 = nums[index];
                return (val1 + val2 )/2;
            }
        }

        private int partition(double[] arr, int left, int right) {
            // 三数取中法 , 随机数在这里写
            int middle = (int)(left+Math.random()*(right-left));
            double pivot = arr[middle];
            // 交换到最右边
            double val = arr[right];
            arr[right] = pivot;
            arr[middle] = val;
            int i = left;
            for (int j = left; j < right; j++) {
                if (arr[j] < pivot) {
                    if (i == j) {
                        ++i;
                    } else {
                        double tmp = arr[i];
                        arr[i++] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            double tmp = arr[i];
            arr[i] = arr[right];
            arr[right] = tmp;
            return i;
        }
    }
}
